package day03

// day03
//
// 416. 分割等和子集
//
// https://leetcode.cn/problems/partition-equal-subset-sum/
//
// ```go
func canPartition(nums []int) bool {
	target := 0
	for _, v := range nums {
		target += v
	}
	if target%2 == 1 {
		return false
	}
	target /= 2
	dp := make([]int, target+1)
	n := len(nums)
	for i := 0; i < n; i++ {
		for j := target; j >= nums[i]; j-- {
			dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
		}
	}
	if target == dp[target] {
		return true
	}
	return false
}

//```

// 1049. 最后一块石头的重量 II
//
// https://leetcode.cn/problems/last-stone-weight-ii/
//
// ```go
func lastStoneWeightII(stones []int) int {
	target := 0
	for _, v := range stones {
		target += v
	}
	sum := target
	target /= 2
	dp := make([]int, target+1)
	n := len(stones)
	for i := 0; i < n; i++ {
		for j := target; j >= stones[i]; j-- {
			dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
		}
	}
	return sum - dp[target] - dp[target]
}

//```

// 494. 目标和
//
// https://leetcode.cn/problems/target-sum/
//
// ```go
func findTargetSumWays(nums []int, target int) int {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	//加法:x 减法:sum-x
	//target = x - (sum-x)
	//x = (target+sum)/2
	n := (target + sum) / 2
	if abs(target) > sum || abs(target+sum)%2 == 1 {
		return 0
	}
	dp := make([]int, n+1)
	dp[0] = 1
	for i := 0; i < len(nums); i++ {
		for j := n; j >= nums[i]; j-- {
			dp[j] += dp[j-nums[i]]
		}
	}
	return dp[n]
}
func abs(i int) int {
	if i < 0 {
		return -i
	}
	return i
}

//```
